/*
Frank
CAU
2019/11/23
*/
#ifndef TREE
#define TREE
#include <stdio.h>
#include <typeinfo>
// variable
#define null 0x0
// 用于进行异常处理的字符串常量
// const char *ERRSTR_NULL = "操作空节点";
// const char *ERRSTR_FORMAT = "节点所在层次存在结构错误";
// const char *ERRSTR_UNRECG = "无效字符";

enum nodeType
{
    N_QUANT,
    N_PRID,
    N_CONJ,
    N_RAWNEG, //否定
    N_UNDEF
};

class variable
{ //变量类
public:
    char _v;
    variable *_next_v;
    variable() : _v('^'), _next_v(null){};
    variable(char var)
    {
        this->_v = var;
        this->_next_v = null;
    }
};

typedef variable *vlist;
void change_alpha(vlist v, char old, char nc)
{ //改变变量列表当中的所有相关变量
    printf(" [将要替换%c]", old);
    while (v != null)
    {
        if (v->_v == old)
        {
            v->_v = nc;
        }
        v = v->_next_v;
    }
}


char get_var(vlist var)
{//由于变量呈链表形式，调用此函数获得某些单变量元素的变量值(Predicates)
    
    if (var != null)
    {
        return var->_v;
    }
}

void show_vlist(vlist vl)
{//显示一个链表
    if (vl == null)
    {
        printf("NULL VARLIST!");
        return;
    }
    else
    {
        printf("(");
        while (vl != null)
        {
            printf("%c", vl->_v);
            vl = vl->_next_v;
        }
        printf(")");
    }
}

vlist new_vars(volatile char *array)
{ //根据形如“xyz”的字符数组产生一个参数列表
    vlist v = null;
    vlist head = null;

    if (array != null && *array != '\0')
    {
        head = new variable(*array);
        v = head;
        array++;
    }
    while (array != null && *array != '\0')
    {
        // 调用变量类的构造函数
        v->_next_v = new variable(*array);
        v = v->_next_v;
        array++;
    }
    return head;
}

//  动态操作占主导
// 采用树形结构
// 方便起见，属性全部设置为公有，若有需要可自行调整
class node
{ // 语法树当中的节点
    // 可能是运算符，量词，谓词或者变量
public:
    node *parent; //父节点
    node *_lc;    //左孩子
    node *_rc;    //右孩子

    nodeType _type;  //节点的种类
    bool _neg;       //是否否定
    char _sym;       //节点符号
    variable *_vars; //节点的参数列表

    node *ascend(); //返回当前节点的父节点，没有则创建一个

    node *descend_lc() { this->descend(true); };  //到达当前节点的左孩子
    node *descend_rc() { this->descend(false); }; //到达当前节点的右孩子
    node *descend(bool left);                     //一个节点

    //以下四个是进行节点类型转换的函数
    // 把一个Undefined类型的节点转化为 某种类型
    node *to_quant(char q, char var);
    node *to_prid(bool neg, char name, vlist vl);
    node *to_conj(char cj);
    node *to_rawneg();
    node *neg() { this->_neg = !(this->_neg); }

    node() : _type(N_UNDEF), _sym('^'), _neg(false), _vars(null), parent(null), _lc(null), _rc(null){};
    ~node();

    node(int type, bool neg, char sym, vlist vars);
};
enum error_type
{
    ERR_UNRECG,   //不可识别
    ERR_NULLNODE, //空节点
    ERR_BADFMT,   //格式错误
    ERR_UNEXPEC,  //其他错误
    ERR_DEFAULT
};
class ParseError
{ //自定义异常类

public:
    // const char *msg;
    error_type type;
    node *ernode;
    ParseError() : type(ERR_DEFAULT), ernode(null){};
    ParseError(error_type e, node *s) : type(e), ernode(s){};
};
void error()
{
    printf("【ERROR】");
    throw ParseError();
}
void error(int type, node *ern)
{ //异常函数
    switch (type)
    {
    case ERR_NULLNODE: //空节点
        printf("【ERR:NULL NODE】\n");
        throw ParseError(ERR_NULLNODE, ern);
    case ERR_UNRECG: //无法识别
        printf("【ERR:UNKNOWN CHAR】\n");
        throw ParseError(ERR_UNRECG, ern);
    case ERR_BADFMT: //格式错误
        printf("【ERR:BAD FORMAT】\n");
        throw ParseError(ERR_BADFMT, ern);
    case ERR_UNEXPEC: //其他错误
        printf("【ERR:UNEXPECTED】\n");
        throw ParseError(ERR_BADFMT, ern);
    }
}

node::node(int type, bool neg, char sym, vlist vars)
{
    // 构造函数
    this->_type = (nodeType)type;
    this->_neg = neg;
    this->_sym = sym;
    this->_vars = vars;
    this->parent = null;
    this->_lc = null;
    this->_rc = null;
}
void show(node *n)
{
    // 显示节点

    if (n == null)
    {   // 注意!可以把null的判断置于子函数当中
        // 减少上层函数的负担
        printf(" [0] ");
        return;
    }
    if (n->_type == N_UNDEF)
    {
        printf(" [U] ");
    }
    else if (n->_type == N_PRID)
    {
        // 否定
        if (n->_neg == true)
        {
            printf(" ~%c", n->_sym);
        }
        else
        {
            printf(" %c", n->_sym);
        }
        show_vlist(n->_vars);
        printf("");
    }
    else if (n->_type == N_RAWNEG)
    {
        if (n->_neg == true)
        {
            // 双重否定表示肯定
            printf(" [~~] ");
        }
        else
        {
            printf(" [~] ");
        }
    }
    else if (n->_type == N_CONJ)
    {
        printf(" [%c] ", n->_sym);
    }
    else if (n->_type == N_QUANT)
    {
        printf(" (%c%c)", n->_sym, get_var(n->_vars));
    }
}
void show_lr(node *n)
{
    // 展示自己以及左右节点
    printf("【节点 ");
    show(n);
    printf("父节点");
    show(n->parent);
    printf(" ");
    printf("左孩子 ");
    show(n->_lc);
    printf("右孩子 ");
    show(n->_rc);
    printf(" 】");
}

// 调用不同类型的构造函数
// 返回堆区对象
// 注意自行删除
node *new_qunt(char q, char var)
{
    return new node(N_QUANT, false, q, new variable(var));
}
node *new_prid(bool neg, char name, char *vars_string)
{
    return new node(N_PRID, false, name, new_vars(vars_string));
}
node *new_conj(char cj)
{
    return new node(N_CONJ, false, cj, null);
}
node *new_rawneg()
{
    return new node(N_RAWNEG, false, '^', null);
}
node::~node()
{
    printf("析构节点：%c\n", this->_sym);
}
// 删除一个节点并且和父节点连接
void delete_merge(node *&n)
{
    node *p = n->parent;
    node *tempc;
    if (n->_rc == null && n->_lc != null && n->parent != null)
    {
        // 因为只有一个子节点默认是左孩子
        // 当符合删除条件时
        printf("删除节点");
        show(n);
        printf("并且连接");
        show_lr(n->parent);
        printf("以及");
        show_lr(n->_lc);
        tempc = n->_lc;
        if (n->parent->_lc == n)
        { //如果当前节点在父节点左侧

            n->parent->_lc = n->_lc; //那么连接父节点的左边到子节点
            // 子节点注册新的父节点
        }
        else
        {
            n->parent->_rc = n->_lc; //right side is the same
        }
        n->_lc->parent = n->parent;
        delete n;
        printf("[删除后父结点");
        show_lr(p);
        printf("子节点");
        show_lr(tempc);
        printf("\n");
    }
    else
    {
        printf("删除节点时出错");
        error(ERR_BADFMT, n);
    }
}

node *node::ascend()
{ //转到当前节点的父节点(or rather, higher level, not neccessarily direct parent node)
    // 临时节点

    show(this);
    node *temp = this;
    printf("上溯至");
    if (temp->parent != null)
    { // 存在父节点
        // 转向父节点
        printf("已有的");
        temp = this->parent;
        // 由于写法限制，这里有两个特殊的返回规则
        // 判断是否需要继续上溯（特殊情况）
        if (temp->_type == N_RAWNEG)
        { //对于最开始产生的否定符号
            // 默认写法当中不带括号
            printf("(+1)");
            // 异常处理
            if (temp->parent == null)
            {
                printf("否定符号上溯时");
            }
            while (temp->parent->_type == N_RAWNEG)
            { //如果之前还有否定符号
                temp = temp->parent;
                printf("(+1)");
            }
            // 跳出了否定符号
            show(temp->parent);
            printf("\n");
            return temp->parent;
        }
        if (temp->_type == N_QUANT)
        { //当前节点的父节点是量词
            //和否定雷同
            // 默认写法当中不带括号
            printf("(+1)");
            // 异常处理
            if (temp->parent == null)
            {
                printf("量词符号上溯时");
            }
            while (temp->parent->_type == N_QUANT)
            { //如果之前还有量词
                // 再上一层
                temp = temp->parent;
                printf("(+1)");
            }
            // 直至跳出量词
            // 返回量词之上的节点
            show(temp->parent);
            printf("\n");
            return temp->parent;
        }
        //对于谓词，连接词，都没有这样的问题
        // 直接返回
        show(temp);
        printf("\n");
        return temp;
    }
    else
    { //没有父节点

        //创建父节点
        node *parent = new node();
        // 默认当前节点是左孩子
        parent->_lc = this;
        this->parent = parent;
        printf("新建父节点");
        show(this->parent);
        printf("\n");
        return parent;
    }
}

node *node::descend(bool left)
{
    show(this);
    printf("下降至");
    if (left == true)
    {
        if (this->_lc != null)
        { //什么都不做
            printf("已有的");
        }
        else
        {
            node *lc = new node();
            // 注册父节点
            printf("新建子节点");
            lc->parent = this;
            this->_lc = lc;
        }
        show(this->_lc);
        printf("\n");
        return this->_lc;
    }
    else
    {
        if (this->_rc != null)
        {
            printf("已有的");
        }
        else
        {
            node *rc = new node();
            printf("注册子节点");
            // 注册父节点
            rc->parent = this;
            this->_rc = rc;
            show(this->_rc);
            printf("\n");
            return rc;
        }
        show(this->_rc);
        printf("\n");
        return this->_rc;
    }
}

node *node::to_conj(char c)
{
    printf("\t******");
    show(this);
    printf("修改为 [%c] \n", c);
    if (this->_type == N_UNDEF)
    {
        this->_type = N_CONJ;
        this->_vars = null;
        this->_sym = c;
        this->_neg = false;
        return this;
    }
    else
    {
        return null; //返回空值供上层处理
    }
}

node *node::to_quant(char q, char var)
{
    printf("\t******");
    show(this);
    printf("修改为 (%c%c) \n", q, var);
    if (this->_type == N_UNDEF)
    {
        this->_type = N_QUANT;
        this->_vars = new variable(var);
        this->_sym = q;
        this->_neg = false;
        return this;
    }
    else
    {
        return null; //返回空值供上层处理
    }
}
node *node::to_prid(bool neg, char name, vlist vl)
{ // 这里实际在上层默认设置了neg = false
    // 显示
    printf("\t******");
    show(this);
    printf("修改为 %c", name);
    show_vlist(vl);
    printf(" \n");

    if (this->_type == N_UNDEF)
    { //未定义
        this->_type = N_PRID;
        // 这里有错
        this->_vars = vl;
        this->_sym = name;
        this->_neg = neg;
        return this;
    }
    else
    {
        return null; //返回空值供上层处理
    }
}
node *node::to_rawneg()
{
    printf("\t******");
    show(this);
    printf("\t修改为 [~] \n");

    if (this->_type == N_UNDEF)
    { //未定义
        this->_type = N_RAWNEG;
        // 这里有错
        this->_vars = null;
        this->_sym = '^';
        this->_neg = false;
        return this;
    }
    else
    {
        return null; //返回空值供上层处理
    }
}
void push_neg_down(node *n)
{ //对于谓词之外的节点
    //利用_neg改变属性
    // 并且使_neg = ture
    // 改变子节点的属性

    if (n->_type == N_RAWNEG)
    {
        //最特殊的情况
        // 如果是原生否定节点
        // 现在 neg == true
        if (n->_neg == false)
        {
            //没有双重否定
            // 正常否定
            // 传递
            printf("\t原生否定节点向下传递");
            show(n->_lc);
            printf("\n");

            if (n->_lc != null)
            {
                n->_lc->neg();
            }
            if (n->_rc != null)
            {
                n->_rc->neg();
            }
        }
        else if (n->_neg == true)
        {
            // 双重否定表示肯定
            // 不向下传递
            // 直接跳过
            printf("跳过双重否定节点\n");
            return;
        }
    }

    if (n->_neg == false)
    { //无需处理
        printf("跳过节点");
        show(n);
        printf("\n");
        return;
    }

    // 去除否定
    if (n->_type == N_PRID)
    {
        //到达叶子节点
        // 保留否定
        printf("谓词");
        show(n);
        printf("被最终否定\n");
        return;
    }

    // 消除否定

    printf("\t被还原的否定节点");
    show(n);

    if (n->_type == N_QUANT)
    {
        switch (n->_sym)
        {
        case '#':
            n->_sym = '@';
            break;
        case '@':
            n->_sym = '#';
            break;
        default:
            break;
        }
    }

    // if(n->_type == N_PRID)
    // {//什么都不做
    // }
    if (n->_type == N_CONJ)
    {
        if (n->_sym == '>')
        {
            printf("蕴含符号未消去");
            error(ERR_BADFMT, n);
        }

        switch (n->_sym)
        {
        case '%':
            n->_sym = '!';
            break;
        case '!':
            n->_sym = '%';
            break;
        default:
            break;
        }
    }

    if (n->_lc != null)
    {
        printf("并向下传递至");
        show(n->_lc);
        n->_lc->neg();
    }
    if (n->_rc != null)
    {
        printf("以及");
        show(n->_rc);
        n->_rc->neg();
    }
    n->_neg = false;
    printf("\n");
    return;
}

#endif